package sol.leetcode;

import java.util.*;

/**
 * Subsets II
 */
public class Issue090 {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        Arrays.sort(nums);
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        subsets(nums, 0, nums.length, new ArrayList<Integer>(), res);
        return res;
    }

    private void subsets(int[] nums, int start, int end, List<Integer> prefix, List<List<Integer>> res) {
        res.add(prefix);
        if (start == end)
            return;

        for (int i = start; i < end; ++i) {
            if (i == start || nums[i] != nums[i - 1]) {
                List<Integer> newPrefix = new ArrayList<Integer>(prefix);
                newPrefix.add(nums[i]);
                subsets(nums, i + 1, end, newPrefix, res);
            }
        }
    }

    public static void main(String[] args) {
        int[] nums = {4,1,0};
        Issue090 sol = new Issue090();
        List<List<Integer>> res = sol.subsetsWithDup(nums);
        System.out.println(res);
    }
}
